// https://leetcode.cn/problems/swap-nodes-in-pairs/
package leet24swapnodesinpair

// Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}
// swapPairs swaps the nodes of a linked list in pairs.
// Given a linked list, swap every two adjacent nodes and return its head.
// You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
// Example 1:
// Input: head = [1,2,3,4]
// Output: [2,1,4,3]
// Example 2:
// Input: head = []
// Output: []
// Example 3:
// Input: head = [1]
// Output: [1]
// Constraints:
// The number of nodes in the list is in the range [0, 100].
// 0 <= Node.val <= 100
// Follow up: Can you solve it using only O(1) extra space?
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// 交换前两个节点
	first := head
	second := head.Next
	first.Next = swapPairs(second.Next)
	second.Next = first
	return second
}
// swapPairsIterative swaps the nodes of a linked list in pairs.
// Given a linked list, swap every two adjacent nodes and return its head.
// You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
// Example 1:
// Input: head = [1,2,3,4]
// Output: [2,1,4,3]
// Example 2:
// Input: head = []
// Output: []
// Example 3:
// Input: head = [1]
// Output: [1]
// Constraints:
// The number of nodes in the list is in the range [0, 100].
// 0 <= Node.val <= 100
// Follow up: Can you solve it using only O(1) extra space?
func swapPairsIterative(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// 创建一个虚拟头节点，方便处理头节点的交换
	dummy := &ListNode{Next: head} // 但是这个dummy其实是没有参与交换的，从head开始交换，此处的dummy作为prev存在，以便最终返回的时候方便。这是个好思路，我们使用他的Next但是他却不参与swap。
	prev := dummy
	current := head
	for current != nil && current.Next != nil {
		// 交换当前节点和下一个节点
		first := current
		second := current.Next
		first.Next = second.Next
		second.Next = first
		prev.Next = second

		// 更新prev和current指针
		prev = first
		current = first.Next
	}
	return dummy.Next
}


func SwapSelf(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// 交换前两个节点
	first := head
	second := head.Next
	realHead := second
	// 交换两个的操作是一个重复的操作
	for first != nil && second != nil {
		// 交换两个节点
		first.Next = second.Next
		second.Next = first
		// 更新指针
		if first.Next == nil || first.Next.Next == nil {
			break
		}
		first = first.Next
		second = first.Next
	}

	return realHead
}